import java.util.ListIterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

public class MyDoublyLinkedList<E> extends MyAbstractSequentialList {

	@Override
	public void add(int index, Object e) {
		if (index < 0 || index > size) {
		      throw new IndexOutOfBoundsException
		        ("Index: " + index + ", Size: " + size);
		    }
		    else if (index == 0) {
		      addFirst(e);
		    }
		    else if (index == size) {
		      addLast(e);
		    }
		    else {
		    	
		      Node<E> current = head.next;
		      for (int i = 0; i < index - 1; i++) {
		        current = current.next;
		      }
		      Node<E> temp = current.next;
		      Node<E> add = new Node(e);
		      current.next = add;
		      add.prev = current;
		      add.next = temp;
		      temp.prev = add;
		      
		      size++;
		    }
		
	}

	@Override
	public void clear() {
		size = 0;
		Node<E> head = new Node(null);
		
	}

	@Override
	public boolean contains(Object e) {
		Node<E> current = head;
		boolean found = false;
		for(int i = 0; i < size -1; i++){
			current = current.next;
			if(e.equals(current.element.toString())){
				found = true;
			}
		}
		return found;
	}

	@Override
	public Object get(int index) {
		if (index < 0 || index > size - 1) {
		      throw new IndexOutOfBoundsException
		        ("Index: " + index + ", Size: " + size);
		    }
		Node<E> current = head;
	//	Node<E> current2 = head;
		
		for(int i = 0 ; i <= index; i++){
			current = current.next;
	}
		/*for(int i = 0 ; i <= size; i++){
			System.out.println( "Node " + i);
			current2 = current2.next;
			System.out.println(current2.element.toString());
		}*/
			
		return current.element.toString();
	}

	@Override
	public int indexOf(Object e) {
		Node<E> current = head;
		int index = -1;
		for(int i = 0; i < size; i ++){
			current = current.next;
			if(e.equals(current.element.toString())){
				index = i;
				i = size;
				return index;
			}
		}
		return index;
	}

	@Override
	public int lastIndexOf(Object e) {
		Node<E> current = head;
		int index = -1;
		for(int i = size - 1; i > 0; i --){
			current = current.prev;
	
			if(e.equals(current.element.toString())){
				index = i;
				i = 0;
			}
			
		}
		return index;
	
	}



	@Override
	public Object set(int index, Object e) {
		if(index < 0 || index >= size()){
			throw new IndexOutOfBoundsException();
		}
		else{ 
			Node<E> current = head;
	      for (int i = 0; i <= index; i++) {
	        current = current.next;	       
	        if(i == index){	     
	        	Node<E> temp = current;
	        	Node<E> change = new Node(e);
	        	change.next = temp.next;
	        	change.prev = temp.prev;
	        	(temp.prev).next = change;
	        	(temp.next).prev = change;
	        	
	        }
	      }
	      
	      return current;
		}
		
	}

	@Override
	public Object getFirst() throws NoSuchElementException {
		Node<E> current = head.next;
		return current;
	}

	@Override
	public Object getLast() throws NoSuchElementException {
		Node<E> current = head.prev;
		return current;
	}

	@Override
	public void addFirst(Object e){
		Node<E> newNode = new Node(e);
		if(head.next == null/* && head.prev == null*/){
			head.next = newNode;
			head.prev = newNode;
			newNode.next = head;
			newNode.prev = head;
			
		}
		else{
			newNode.next = head.next;
			newNode.prev = head;
			(head.next).prev = newNode;
			head.next = newNode;
				
		}
	
		size ++;
	
	}
	@Override 
	public void addLast(Object e){
		Node<E> newNode = new Node(e);
		if(head.next == null /*&& head.prev == null*/){
			head.next = newNode;
			head.prev = newNode;
			newNode.next = head;
			newNode.prev = head;
		}
		else{
		newNode.prev = head.prev;
		newNode.next = head;
		(head.prev).next = newNode;
		head.prev = newNode;
		}
		size ++;
	}
	@Override
	public Object remove(int index) {
		if(index < 0 || index >= size()){
			throw new IndexOutOfBoundsException();
		}
			    if (index == 0) {
			      return removeFirst();
			    }
			    else if (index == size - 1) {
			      return removeLast();
			    }
			    else {
			      Node<E> current = head.next;
			      
			      for (int i = 0; i < index - 1; i++) {
			        current = current.next;
			      }
			      Node<E> temp = current.next;
			      
			      (temp.prev).next = temp.next;
			      (temp.next).prev = temp.prev; 
			      
			      size--;
			      return temp/*.element*/;
			    }
	}
	@Override
	public Object removeFirst() throws NoSuchElementException {
		if( head.next == null){
			throw new NoSuchElementException();
		}
		else{
		Node<E> newNode = head.next;
		(newNode.prev).next = newNode.next;
		(newNode.next).prev = newNode.prev;
		size --;
		
		
		return newNode;
		}
	}

	@Override
	public Object removeLast() throws NoSuchElementException {
		if( head.prev == null){
			throw new NoSuchElementException();
		}
		else{
		Node<E> newNode = head.prev;
		(newNode.prev).next = newNode.next;
		(newNode.next).prev = newNode.prev;
		size --;
		
		return newNode;
		}
	}

	private static class Node<E> {
		 E element;
		 Node<E> next;
		 Node<E> prev;

		public Node(E element) {
			this.element = element;
			this.next = next;
			this.prev = prev;
		}
	}
	
	public MyDoublyLinkedList() {
		Node<E> head = new Node(null);
		head.next = head;
		head.prev = head;
  }
	private Node<E> head = new Node(null);
	@Override
	public ListIterator listIterator(int index) {
	
		return null;
	}//end inner classes
	@Override /** Override toString() to return elements in the list */
	  public String toString() {
	    StringBuilder result = new StringBuilder("[");

	    Node<E> current = head.next;
	    for (int i = 0; i < size; i++) {
	      result.append(current.element);
	      current = current.next;
	      if (i < size-1) {
	        result.append(", "); // Separate two elements with a comma
	      }
	      else {
	        result.append("]"); // Insert the closing ] in the string
	      }
	    }

	    return result.toString();
	  }

}
